import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网面试必刷Top101之堆/栈/队列
 */
public class Test {
    /**
     * 用两个栈实现队列
     */
    /*Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    //对于用两个栈实现队列来说，我们需要让一个栈作为存储，一个栈作为弹出时需要
    public void push(int node) {
        //我们选择让stack1作为存储的栈
        stack1.push(node);
    }

    public int pop() {
        if(stack1.empty() && stack2.empty()) {
            return -1;
        }
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }*/

    /**
     * 包含min函数的栈
     */
    /*private int[] elem = new int[10];
    private int size = 0;
    private int min = 10001;
    //创建一个队列，用于存储历次最小值
    private Stack<Integer> stackmin = new Stack<>();

    public void push(int node) {
        // write code here
        if(size >= elem.length) {
            //注意，位运算符的优先级 < +-
            elem = Arrays.copyOf(elem,elem.length + (elem.length>>>1));
        }
        if(node <= min) {
            min = node;
            stackmin.push(node);
        }
        elem[size++] = node;
    }

    public void pop() {
        if(size == 0) {
            return;
        }
        if(elem[size - 1] == min) {
            stackmin.pop();
            min = stackmin.peek();
        }
        size--;
    }

    public int top() {
        return elem[size - 1];
    }

    public int min() {
        return min;
    }*/

    /**
     * 有效括号序列(判断一个字符串中"()"，"[]","{}"能否一一对应(可以嵌套，但不能交叉))
     * 思路：
     * 内层括号与内层括号对应，外层括号和外层括号对应
     * 因此我们选择创建一个栈，用来存放左括号
     * 然后当遍历字符串遇到右括号的时候与栈顶元素比较，对应弹出，不对应return false
     * 最后判断栈是否为空
     */
    /*public boolean isValid (String s) {
        // write code here
        if(s == null) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                //如果是右括号，与stack的栈顶元素进行比较
                if(stack.empty()) {
                    return false;
                }else {
                    //在栈不为空的情况下进行判断
                    if((stack.peek() == '(' && c == ')')
                            || (stack.peek() == '[' && c == ']')
                            || (stack.peek() == '{' && c == '}')) {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        if(!stack.empty()) {
            return false;
        }
        return true;
    }*/

    /**
     * 滑动窗口的最大值
     * 方法一：建立优先级队列
     * 入堆时机：只要窗口移动到了，就入
     * 出堆时机：只要堆顶元素还在窗口，就不出
     * @param num
     * @param size
     * @return
     */
    /*public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(size > num.length || num.length == 0 || size == 0) {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        //注意实例化比较器时声明成员类型后面的“()”
        //建立大根堆elem2[0] - elem1[0]
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] elem1, int[] elem2) {
                return (elem1[0] != elem2[0]) ? (elem2[0] - elem1[0]) : (elem1[1] - elem2[1]);
            }
        });
        //先将前size个元素入堆
        for(int i = 0; i < size; i++) {
            queue.offer(new int[]{num[i],i});
        }
        int slow = 0;
        int fast = size;
        list.add(queue.peek()[0]);
        while(fast < num.length) {
            slow++;
            queue.offer(new int[]{num[fast],fast});
            while(queue.peek()[1] < slow) {
                queue.poll();
            }
            list.add(queue.peek()[0]);
            fast++;
        }
        return list;
    }*/

    /**
     * 滑动窗口的最大值
     * 方法二：双端队列
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(num.length == 0 || size == 0 || size > num.length) {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < size; i++) {
            while(!deque.isEmpty()) {
                if(deque.peekLast() <= num[i]) {
                    deque.pollLast();
                }else {
                    deque.offerLast(num[i]);
                    break;
                }
            }
            //不止是在第一次插入时用到，当新进入窗口的值是最大值时
            //上面的while循环会将队列中所有元素全部出队
            //因此必须在后面兜底，保证一旦遇到第二种情况可以将最新的元素入队
            if(deque.isEmpty()) {
                deque.offerLast(num[i]);
            }
        }
        int slow = 0;
        int fast = size;
        list.add(deque.peekFirst());
        while(fast < num.length) {
            if(num[slow] == deque.peekFirst()) {
                deque.pollFirst();
            }
            slow++;
            while(!deque.isEmpty()) {
                if(deque.peekLast() <= num[fast]) {
                    deque.pollLast();
                }else {
                    deque.offerLast(num[fast]);
                    break;
                }
            }
            if(deque.isEmpty()) {
                deque.offerLast(num[fast]);
            }
            list.add(deque.peekFirst());
            fast++;
        }
        return list;
    }

    /**
     * 最小的 k 个数，不考虑顺序
     * topk 问题
     * @param input
     * @param k
     * @return
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //先考虑边界条件
        if(input.length < k || k == 0) {
            return new ArrayList<Integer>();
        }
        //创建k个元素大小的大根堆，需要传入比较器
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer e1,Integer e2) {
                return e2 - e1;
            }
        });
        for(int i = 0; i < k; i++) {
            pq.offer(input[i]);
        }
        for(int i = k; i < input.length; i++) {
            if(input[i] < pq.peek()) {
                pq.poll();
                pq.offer(input[i]);
            }
        }
        return new ArrayList<Integer>(pq);
    }

    /**
     * 寻找第 K 大元素
     * 快排方法，时间复杂度：O(NlogN)，空间复杂度：O(1)（实际需要递归O(N))
     * @param a
     * @param n
     * @param K
     * @return
     */
    public int findKth(int[] a, int n, int K) {
        // write code here
        //思路：快排，每次快排都能确定一个元素的位置
        //再根据确定的元素位置判断接下来是走左边还是走右边或者就是当前位置
        //由于找第 k 大，选择降序排序
        return qsort_findIndex(a, 0, n - 1, K);
    }

    private int qsort_findIndex(int[] num, int left, int right, int K) {
        if(left > right) {
            return -1;
        }
        //快排挖坑法
        int tmp = num[left];
        int i = left;
        int j = right;
        //比较
        while(i < j) {
            //注意考虑数组首尾元素相同的情况
            while(i < j && num[j] <= tmp) {
                j--;
            }
            num[i] = num[j];
            while(i < j && num[i] >= tmp) {
                i++;
            }
            num[j] = num[i];
        }
        num[i] = tmp;
        if(i + 1 == K) {
            return num[i];
        }else if(i + 1 < K) {
            return qsort_findIndex(num, i + 1, right, K);
        }else {
            return qsort_findIndex(num, left, i - 1, K);
        }
    }

    /**
     * 寻找第K大元素
     * 堆方法，时间复杂度：0(NlogK)，空间复杂度：O(K)
     * @param a
     * @param n
     * @param K
     * @return
     */
    public int findKth2(int[] a, int n, int K) {
        // write code here
        //思路二：堆排，创建大小为 K 的小根堆
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int i = 0; i < K; i++) {
            pq.offer(a[i]);
        }
        for(int i = K; i < n; i++) {
            if(a[i] > pq.peek()) {
                pq.poll();
                pq.offer(a[i]);
            }
        }
        return pq.peek();
    }


    /**
     * 数据流中的中位数
     * 大根堆和小根堆配合，分别存储一半的数据
     */
    //一个堆保证比另一个堆的数据都大，要得到这个堆的最小值，创建小根堆
    PriorityQueue<Integer> pqLarge = new PriorityQueue<>();
    //一个堆保证比另一个堆的数据都小，要得到这个堆的最大值，创建大根堆
    PriorityQueue<Integer> pqSmall = new PriorityQueue<>(new Comparator<Integer>() {
        public int compare(Integer e1, Integer e2) {
            return e2 - e1;
        }
    });
    public void Insert(Integer num) {
        //当两个堆都为空时，先往小的堆里面存放值
        //当小的堆不为空时，仍然往小的堆里存放数据

        //但是当两个堆之间 size 差值 > 0时，先往小的堆里存放数据，再将小的堆中堆顶元素出堆放到大的堆中
        //保证存入大的堆中的数据一定是大于小根堆中所有的数据的
        //同理，当是直接往小的堆中存放数据时，存放完也需要判断小的堆的堆顶元素是否大于大的堆的堆顶元素

        //最后得到的结果如果所有数据加起来和为奇数，结果就是小的堆的堆顶元素
        //如果是偶数，结果就是两个堆的堆顶元素之和的平均值
        if(pqSmall.size() - pqLarge.size() > 0) {
            pqSmall.offer(num);
            pqLarge.offer(pqSmall.poll());
        }else {
            pqSmall.offer(num);
            if(!pqLarge.isEmpty() && pqSmall.peek() > pqLarge.peek()) {
                pqSmall.offer(pqLarge.poll());
                pqLarge.offer(pqSmall.poll());
            }
        }
    }

    public Double GetMedian() {
        int size1 = pqLarge.size();
        int size2 = pqSmall.size();
        if((size1 + size2) % 2 == 1) {
            return (double)pqSmall.peek();
        }else {
            return ((double)(pqSmall.peek() + pqLarge.peek())) / 2;
        }
    }

    /**
     * 表达式求值
     * 方法一：栈 + 递归
     */
    int i = 0;
    public int solve (String s) {
        // write code here
        if(s == null || s.length() == 0) {
            return 0;
        }
        //创建一个栈，用来存储数据
        Stack<Integer> stack = new Stack<Integer>();
        int size = s.length();
        //返回条件
        while(i < size && s.charAt(i) != ')') {
            //进来之后可能有三种情况
            //1. 遇见左括号，递归，并将返回值入栈
            if(s.charAt(i) == '(') {
                i++;
                stack.push(solve(s));
                continue;
            }
            //2. 遇见双目运算符
            //可能情况又分三种
            // + 或 -，这种情况下我们最好提前定义一个数字表示+-，默认是正，后面可能是'('，需要判断
            int tmp = 1;
            //num是在运算符为'*'的时候，存储出栈元素所用
            int num = 1;
            //遇到 * ，出栈一个元素并判断后面的元素是否为'('
            //只要递归调用了方法，都应该continue，保证i < size
            if(s.charAt(i) == '+') {
                i++;
                if(s.charAt(i) == '(') {
                    i++;
                    stack.push(solve(s));
                    continue;
                }
            }else if(s.charAt(i) == '-') {
                tmp = -1;
                i++;
                if(s.charAt(i) == '(') {
                    i++;
                    stack.push(-solve(s));
                    continue;
                }
            }else if(s.charAt(i) == '*') {
                i++;
                if(s.charAt(i) == '(') {
                    i++;
                    stack.push(stack.pop() * solve(s));
                    continue;
                }else {
                    num = stack.pop();
                }
            }

            //3. 遇到数字时，我们需要保存字符串数字开始和结束的位置
            //然后进行截取并转成数字
            int j = 0;
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                j = i++;
                //这里必须加i 与 size的比较，因为 i++ 之后有可能越界
                while(i < size && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    i++;
                }
                //截取j - i部分的字符串并转成数字
                String tmpS = s.substring(j,i);
                int ans = Integer.parseInt(tmpS) * num * tmp;
                //将计算后数据入栈
                stack.push(ans);
            }
        }
        //循环结束时，如果碰到的是右括号，那么应该i++，保证递归回去后，上一层不会碰到这个右括号
        if(i < size) {
            i++;
        }
        int sum = 0;
        while(!stack.empty()) {
            sum += stack.pop();
        }
        return sum;
    }
}
